data=[1,0,2,1,0,0,1,2,2,1,0,2]
i=0
start=0
end=len(data)-1
while i<end:
    if data[i]==0:
        tmp=data[start]
        data[start]=data[i]
        data[i]=tmp
        start=start+1
    elif data[i]==2:
        tmp=data[end]
        data[end]=data[i]
        data[i]=tmp
        end=end-1
    else:
        i=i+1
print(data)
list=[1,0,2,1,0,0,1,2,2,1,0,2]

class ListBean:
    def __init__(self,data,next):
        super().__init__()
        self.data=data
        self.next=next
def printLinkList(head):
    print("*****************************")
    current=head
    while True:
        current=current.next
        if current!=None:
            print(current.data)
        else:
            break
def method2(list):
    head=ListBean(None,None)
    lastData=head
    for i in list:
        lastData.next=ListBean(i,None)
        lastData=lastData.next
    return head

def sortLinkList(linkList):
    redLink=ListBean(None,None)
    whiteLink=ListBean(None,None)
    blueLink=ListBean(None,None)
    lastIndex=linkList.next
    lastRed=redLink
    lastWhite=whiteLink
    lastBlue=blueLink
    while(lastIndex!=None):
        if lastIndex.data==0:
            lastRed.next=lastIndex
            lastRed=lastRed.next
        elif lastIndex.data==1:
            lastWhite.next=lastIndex
            lastWhite=lastWhite.next
        elif lastIndex.data==2:
            lastBlue.next=lastIndex
            lastBlue=lastBlue.next
        lastIndex=lastIndex.next
    linkList.next=redLink.next
    lastRed.next=whiteLink.next
    lastWhite.next=blueLink.next
            
newLinkedList=method2(list)
printLinkList(newLinkedList)
sortLinkList(newLinkedList)
printLinkList(newLinkedList)
